package leetcode.recursion;

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * leetCode 698
 * Partition to K Equal Sum Subsets
 * 划分为k个相等的子集
 * 思路：将数组nums划分为k个子集，每个子集和为nums/k。 设置一个vector<int> flag来记录nums数组内元素的使用情况

 */
public class Recursion698 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            List<Integer> input = Arrays.stream(str.split(",")).map(i -> { return Integer.parseInt(i); }).collect(Collectors.toList());
            System.out.println(Arrays.toString(input.toArray()));
            Integer [] nums = input.toArray(new Integer[input.size()]);
            new Recursion698().canPartitionKSubsets(nums, 1);
        }
    }
    public boolean canPartitionKSubsets(Integer[] nums, int k) {
        int sum = 0;
        for(int i = 0 ; i< nums.length;i++) sum += nums[i];;
        if(sum%k != 0 || sum <= 0) return false;
        int target = sum/k;
        // flag表示数字是否已用
        boolean [] flag = new boolean[nums.length];
        int curSum = 0;
        return dfs(nums, flag, 0, 0, k, curSum, target);
    }
    // start表示搜索的起点，n为当前已经搜索过的数字数目，curSum为当前的累加和，target，k,flag
    public boolean dfs(Integer[] nums, boolean [] flag, int start, int n, int k, int curSum, int target){
        if(curSum > target) return false;
        if(k == 0 && n == nums.length) return true;
        //已经存在一个集合,//继续从第一个数字开始搜索,start变为0,当前和变为0
        if(curSum == target){
            return dfs(nums, flag, 0, n, k - 1, 0, target);
        }
        for(int i = start ; i < nums.length ; i++){
            if(flag[i]) continue;
            flag[i] = true;
            //还是给第k个子集找值,所以k不变;要把i处的值加上，并从他的下一个位置搜索
            if(dfs(nums, flag, i + 1, n + 1, k, curSum+nums[i], target)){
                return true;
            }
            //说明上述子集中没有用到i,所以恢复状态等待下次使用
            flag[i] = false;
        }
        return false;
    }
}
